package com.solution;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 25. K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 *
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 示例：
 *
 * 给你这个链表：1->2->3->4->5
 *
 * 当 k = 2 时，应当返回: 2->1->4->3->5
 *
 * 当 k = 3 时，应当返回: 3->2->1->4->5
 *
 * @author LiYongKui
 * @version 1.0
 * @date 2021/1/27 14:52
 */
public class Solution0025 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static ListNode reverseKGroup1(ListNode head, int k) {
        ListNode pre = new ListNode(0);
        ListNode tmp = pre;
        Deque<ListNode> stack = new LinkedList<>();
        int i = 1;
        while(head != null){
            stack.push(head);
            head = head.next;
            i++;
            if(stack.size() == k){
                while(stack.peek() != null){
                    ListNode node = stack.pop();
                    node.next = null;
                    tmp.next = node;
                    tmp = tmp.next;
                }
                i = 1;
            }
        }
        if(!stack.isEmpty()){
            while(stack.peek() != null){
                ListNode node = stack.pollLast();
                node.next = null;
                tmp.next = node;
                tmp = tmp.next;
            }
        }
        return pre.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre = new ListNode(0, head);
        ListNode tmp = pre;
        while(head != null){
            ListNode cur = head;
            for (int i = 1; i < k; i++) {
                cur = cur.next;
                if(cur == null){
                    return pre.next;
                }
            }
            ListNode next = cur.next;
            ListNode[] reverse = reverse(head,cur);
            head = reverse[0];
            cur = reverse[1];
            // 把子链表重新接回原链表
            tmp.next = head;
            cur.next = next;
            tmp = cur;
            head = cur.next;
        }
        return pre.next;
    }

    private static ListNode[] reverse(ListNode head, ListNode cur) {
        ListNode prev = cur.next;
        ListNode p = head;
        while(prev != cur){
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{cur,head};
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3)));
        ListNode result = reverseKGroup(head,2);
        System.out.println();
    }
}
